package com.example.demo.leetcode.zuocheng.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/10 14:59
 */
public class String_一个字符串的全排列 {

    /**
     *  index从0开始递归,index表示被交换的位置
     *  每个index, 从index->最后一位，都有机会和index交换位置，交换后进入下一层递归
     *  每个index层可能交换的位置-> arr[index.......length-1]
     *  结束条件: index == arr.length
     *  使用set可以去重
     * @param arr
     * @param index
     * @param res
     */
    public static void allStr(char [] arr, int index, List<String> res){

        if(index == arr.length){
            res.add(String.valueOf(arr));
            return;
        }
        //每一层可以使用set过滤
        HashSet<Character> set = new HashSet<>();
        for(int i=index;i<arr.length;i++){
            if(set.contains(arr[i])){
                continue;
            }
            set.add(arr[i]);

            swap(arr,index,i);
            allStr(arr,index+1,res);
            swap(arr,index,i);

        }
    }

    public static void swap(char [] arr , int i,int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        String a = "abcd";
        List<String> list =new ArrayList<>();
        allStr(a.toCharArray(),0,list);
        for(String temp : list){
            System.out.println(temp);
        }
    }

}
